<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(A卷,200分)- 区块链文件转储系统（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>区块链底层存储是一个链式文件系统&#xff0c;由顺序的N个文件组成&#xff0c;每个文件的大小不一&#xff0c;依次为F1,F2,...,Fn。随着时间的推移&#xff0c;所占存储会越来越大。</p> 
<p>云平台考虑将区块链按文件转储到廉价的SATA盘&#xff0c;只有连续的区块链文件才能转储到SATA盘上&#xff0c;且转储的文件之和不能超过SATA盘的容量。</p> 
<p>假设每块SATA盘容量为M&#xff0c;求能转储的最大连续文件之和。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>第一行为SATA盘容量M&#xff0c;1000 ≤ M ≤ 1000000</p> 
<p>第二行为区块链文件大小序列F1,F2,...,Fn。其中 1 ≤ n ≤ 100000&#xff0c;1 ≤ Fi ≤ 500</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>求能转储的最大连续文件大小之和</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">1000<br /> 100 300 500 400 400 150 100</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">950</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">最大序列和为950&#xff0c;序列为[400,400,150]</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">1000<br /> 100 500 400 150 500 100</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">1000</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">最大序列和为1000&#xff0c;序列为[100,500,400]</td></tr></tbody></table> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>由于本题需要求解最大<span style="color:#fe2c24;"><strong>连续</strong></span>文件大小之和&#xff0c;因此可以考虑使用双指针&#43;滑动窗口来解题。</p> 
<p>本题的滑动窗口的左边界l,右边界r的运动逻辑如下&#xff1a;</p> 
<ul><li>如果滑动窗口内部和 &lt; m&#xff0c;则r&#43;&#43;</li><li>如果滑动窗口内部和 &gt; m&#xff0c;则l&#43;&#43;</li><li>如果滑动窗口内部和 &#61; m&#xff0c;则已得到最大值&#xff0c;直接返回m即可。</li></ul> 
<p>在计算滑动窗口内部和的过程中&#xff0c;如果r&#43;&#43;&#xff0c;则说明内部和可能会增大产生最大值&#xff0c;因此我们需要在r&#43;&#43;时&#xff0c;判断并保留最大值。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 2) {
    const m &#61; lines[0] - 0;
    const F &#61; lines[1].split(&#34; &#34;).map(Number);

    console.log(getResult(m, F));
    lines.length &#61; 0;
  }
});

function getResult(m, F) {
  let l &#61; 0,
    r &#61; 0;

  let n &#61; F.length;

  let sum &#61; 0;
  let max &#61; 0;

  while (r &lt; n) {
    // 尝试右指针右移一下的新和&#xff08;注意初始时右指针右移后指向0&#xff09;
    const newSum &#61; sum &#43; F[r];

    // 如果新和超过了m&#xff0c;即SATA盘容量&#xff0c;则右指针不能右移&#xff0c;并且还需要左指针右移来减少旧和
    if (newSum &gt; m) {
      sum -&#61; F[l&#43;&#43;]; // 左指针右移只会减少旧和&#xff0c;因此不会产生最大值
    }
    // 如果新和小于m&#xff0c;则当前尝试的右指针右移可行&#xff0c;因此 sum &#43;&#61; F[r]&#xff0c;并且我们下一步还可以继续尝试让右指针右移&#xff0c;即r&#43;&#43;
    else if (newSum &lt; m) {
      sum &#43;&#61; F[r&#43;&#43;];
      max &#61; Math.max(sum, max); // 右指针右移时会增加旧和&#xff0c;因此可能会产生最大值
    }
    // 如果新和等于m&#xff0c;那么说明已经找到了一个容量和SATA盘相同的连续文件大小&#xff0c;即此时已经是最大值了&#xff0c;可以直接返回
    else {
      return m;
    }
  }

  return max;
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.Arrays;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int m &#61; Integer.parseInt(sc.nextLine());
    Integer[] f &#61;
        Arrays.stream(sc.nextLine().split(&#34; &#34;)).map(Integer::parseInt).toArray(Integer[]::new);

    System.out.println(getResult(m, f));
  }

  public static int getResult(int m, Integer[] f) {
    int l &#61; 0, r &#61; 0;
    int sum &#61; 0, max &#61; 0;

    int n &#61; f.length;

    while (r &lt; n) {
      // 尝试右指针右移一下的新和&#xff08;注意初始时右指针右移后指向0&#xff09;
      int newSum &#61; sum &#43; f[r];

      // 如果新和超过了m&#xff0c;即SATA盘容量&#xff0c;则右指针不能右移&#xff0c;并且还需要左指针右移来减少旧和
      if (newSum &gt; m) {
        sum -&#61; f[l&#43;&#43;]; // 左指针右移只会减少旧和&#xff0c;因此不会产生最大值
      }
      // 如果新和小于m&#xff0c;则当前尝试的右指针右移可行&#xff0c;因此 sum &#43;&#61; F[r]&#xff0c;并且我们下一步还可以继续尝试让右指针右移&#xff0c;即r&#43;&#43;
      else if (newSum &lt; m) {
        sum &#43;&#61; f[r&#43;&#43;];
        max &#61; Math.max(sum, max); // 右指针右移时会增加旧和&#xff0c;因此可能会产生最大值
      }
      // 如果新和等于m&#xff0c;那么说明已经找到了一个容量和SATA盘相同的连续文件大小&#xff0c;即此时已经是最大值了&#xff0c;可以直接返回
      else {
        return m;
      }
    }

    return max;
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python">m &#61; int(input())
f &#61; list(map(int, input().split()))


def getResult(m, f):
    l &#61; 0
    r &#61; 0
    n &#61; len(f)

    sum &#61; 0
    maxV &#61; 0

    while r &lt; n:
        # 尝试右指针右移一下的新和&#xff08;注意初始时右指针右移后指向0&#xff09;
        newSum &#61; sum &#43; f[r]

        # 如果新和超过了m&#xff0c;即SATA盘容量&#xff0c;则右指针不能右移&#xff0c;并且还需要左指针右移来减少旧和
        if newSum &gt; m:
            # 左指针右移只会减少旧和&#xff0c;因此不会产生最大值
            sum -&#61; f[l]
            l &#43;&#61; 1
        # 如果新和小于m&#xff0c;则当前尝试的右指针右移可行&#xff0c;因此 sum &#43;&#61; F[r]&#xff0c;并且我们下一步还可以继续尝试让右指针右移&#xff0c;即r&#43;&#43;
        elif newSum &lt; m:
            sum &#43;&#61; f[r]
            r &#43;&#61; 1
            maxV &#61; max(sum, maxV) # 右指针右移时会增加旧和&#xff0c;因此可能会产生最大值
        # 如果新和等于m&#xff0c;那么说明已经找到了一个容量和SATA盘相同的连续文件大小&#xff0c;即此时已经是最大值了&#xff0c;可以直接返回
        else:
            return m

    return maxV


print(getResult(m, f))
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>